Sum-of-squares optimization techniques have been successfully applied by researchers in the control engineering field.[1][2][3]
A sum-of-squares program is an optimization problem with a linear cost and a particular type of constraint on the decision variables. These constraints are of the form that when the dexision variables are used as coefficients in certain polynomials, those polynomials should have the polynomial SOS property.[4] The problem can be expressed as:
subject to
Here "SOS" represents the class of SOS polynomials. The vector and polynomials are given as part of the data for the optimization problem. The quantities are the decision variables. SOS programs can be converted to semidefinite programs (SDPs) using the connection between SOS polynomials and positive-semidefinite matrices.
A polynomial is a sum of squares (SOS) if there exist polynomials such that . For example,
is a sum of squares since
where
Note that if is a sum of squares then for all . Detailed descriptions of polynomial SOS are available.[5][6][7]
Quadratic forms can be expressed as where is a symmetric matrix. Similarly, polynomials of degree ≤ 2d can be expressed as
where the vector contains all monomials of degree . This is known as the Gram matrix form. An important fact is that is SOS if and only if there exists a symmetric and positive-semidefinite matrix such that . This provides a connection between SOS polynomials and positive-semidefinite matrices.